package algorithm
{
	import datastructure.Edge;
	import datastructure.Graph;
	import datastructure.Vertex;

	/**
	 * 最著名的单起点最短路径算法： Dijkstra算法
	 * @author juxuan
	 * 
	 */	
	public class Dijkstra
	{
		private var paths:Array;	//单起点最短路径集合
		private var vt:Array;	//已在路径集合的顶点集合
		
		private var graph:Graph;
		private var startVert:Vertex;
		private var priorityQueues:Array;
		
		
		public function Dijkstra(g:Graph,start:Vertex,originVerArray:Array)
		{
			this.paths = new Array();
			this.vt = new Array();
			this.priorityQueues = new Array();
			this.graph = g;
			this.startVert = start;
			this.startVert.isStart = true;
			
			this.initialize(originVerArray);
		}
		
		public function getVT():Array
		{
			return this.vt;
		}
		
		public function getPaths():Array
		{
			return this.paths;
		}
		
		public function getPathsShow():String
		{
			var pathsShow:String = "";
			
			for(var i:int = 1; i < this.vt.length; i++)
			{
				pathsShow += "从" + this.startVert.name + "到" + this.vt[i].name + ":";
				
				pathsShow = pathsShow + this.getVertexPath(this.vt[i]) + ";长度为:" + this.vt[i].closestDist + '\n';
			}
			return pathsShow;
		}
		
		
		public function getVertexPath(vert:Vertex):String
		{
			var v:Vertex = vert;
			var vpath:String = "";
			vpath = v.name;
			while(v.closestVer != null)
			{
				vpath = v.closestVer.name + "-" + vpath;
				v = v.closestVer;
			}
			return vpath;
		
		}
		
		/**
		 * 运行 Dijkstra算法
		 * 
		 */		
		public function runDijkstra():void
		{
			for(var i:int = 0;i < this.graph.verNum();i++)
			{
				var u:Vertex = this.priorityQueues.shift();	//删除优先级最小的元素
				this.vt.push(u);
				if(u.closestVer != null)
				{
					var edge:Edge = new Edge(u.closestVer,u,this.graph.weight(u.closestVer.index,u.index));
					this.paths.push(edge);
				}
				
				this.resetPriorityQueues(u,this.priorityQueues);
			}
		}
		
		
		/**
		 * 初始化优先队列中顶点的优先级 
		 * @param originVerArray
		 * 
		 */		
		private function initialize(originVerArray:Array):void
		{
			for(var i:int = 0; i < originVerArray.length;i++)
			{
				if(originVerArray[i].index == this.startVert.index)
				{
					originVerArray[i].closestDist = 0;	//开始顶点的优先级为最小，0
				}
				else
				{
					originVerArray[i].closestDist = int.MAX_VALUE;
				}
				originVerArray[i].closestVer = null;
				this.priorityQueues.push(originVerArray[i]);
			}
			
			this.priorityQueues.sortOn("closestDist",Array.NUMERIC);	
		}
		
		
		/**
		 * 重新设置优先队列中顶点的优先级 
		 * @param priorityQueues
		 * 
		 */		
		private function resetPriorityQueues(u:Vertex,pq:Array):void
		{
			for(var i:int = 0; i < pq.length; i++)
			{
				var weight:int = this.graph.weight(u.index,pq[i].index);
				if(weight != 0)
				{
					if((u.closestDist + weight) < pq[i].closestDist)
					{
						pq[i].closestDist = u.closestDist + weight;
						pq[i].closestVer = u;
					}
				}
			}
			pq.sortOn("closestDist",Array.NUMERIC);
			
		}
		
		
		
		
		
		
		
		
		
		
		
		
	}
}